package 剑指offer;

public class _12矩阵中的路径 {
    public boolean exist(char[][] board, String word) {
        char[] word_array = word.toCharArray();
        for(int i = 0; i < board.length; i++){
            for(int j= 0; j < board[0].length; j++){
                if(fun(board,i,j,word_array,0) == true){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean fun(char[][] board, int i, int j, char[] word_array, int k){
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != word_array[k]){
            return false;
        }
        if(k == word_array.length - 1){
            return true;
        }
        board[i][j] = '0';
        boolean flag = fun(board,i + 1,j,word_array,k + 1) || fun(board,i - 1,j,word_array,k + 1)
                ||fun(board,i,j + 1,word_array,k + 1) || fun(board,i,j - 1,word_array,k + 1);
        board[i][j] = word_array[k];
        return flag;
    }
}
